#include <math.h>
#include <cmath>
#include <vector>
#include <stdlib.h>

#include "geometry.h"

namespace 
{
   double distance(point a, point b, point c)
   {
      double h = pow((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x), 2);
      h /= (b.x - c. x) * (b.x - c. x) + (b.y - c.y) * (b.y - c.y);
      return h;
   }
}

std::vector<int> douglas_peucker(const std::vector<point> &chain, double eps, int first, int last)
{
   double dmax = 0;
   int imax = 0;
   int chain_size = chain.size() - 1;
   if (chain_size == 1)
   {
      std::vector<int> result;
      result.push_back(first);
      result.push_back(last);
      return result;
   }
   for (int i = 1; i < chain_size; i++)
   {
      double dis = distance(chain[i], chain[0], chain[chain_size]);
      if (dis > dmax)
      {
         dmax= dis;
         imax= i;
      }
   }

   if (dmax > eps)
   {
      std::vector<point> chain1;
      for (int i = 0; i <= imax; i++)
      {
         chain1.push_back(chain[i]);
      }
      std::vector<int> result = douglas_peucker(chain1, eps, first, first + imax); 
      
      std::vector<point> chain2;
      for (int i = imax; i <= chain_size; i++)
      {
         chain2.push_back(chain[i]);
      }
      std::vector<int> result1 = douglas_peucker(chain2, eps, first + imax, last);
      
      int result1_size = result1.size();
      for (int i = 1; i < result1_size; i++)
      {
         result.push_back(result1[i]);
      }
      return result;
   }

   std::vector<int> result;
   result.push_back(first);
   result.push_back(last);
   return result;
}